package a_doubleWrite;

import util.ListNode;
import util.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 95. 不同的二叉搜索树 II
 * 给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。
 * 可以按 任意顺序 返回答案。
 *
 * @author: luolidong
 * @create: 2021-07-23 15:06
 * @version: 1.0
 */
public class L95_1 {
    public List<TreeNode> generateTrees(int n) {
        //相当于1-n,作为根节点，
        return generateTrees(1, n);
    }

    List<TreeNode> generateTrees(int left, int right) {
        List<TreeNode> list = new ArrayList<>();
        if (left > right) {
            list.add(null);
            return list;
        }
        for (int i = left; i <= right; i++) {
            List<TreeNode> leftList = generateTrees(left, i - 1);
            List<TreeNode> rightList = generateTrees(i + 1, right);

            //选一个左侧的，选一个右侧
            for (TreeNode l : leftList) {
                for (TreeNode r : rightList) {
                    TreeNode node = new TreeNode(i);
                    node.left = l;
                    node.right = r;
                    list.add(node);
                }
            }
        }
        return list;
    }
}
